Minimization of conjunctive normal forms of boolean functions by combinatorial method

Authors

DOI:

https://doi.org/10.15587/2312-8372.2018.146312

Keywords:

minimization of conjunctive normal forms, combinatorial method of minimizing Boolean functions, block diagram with repetition

Abstract

The object of research is the combinatorial method of minimizing conjunctive normal forms (CNF) of Boolean functions in order to reduce its algorithmic complexity. One of the most places to minimize CNF of Boolean functions is the complexity of the minimization algorithm and the guarantee of obtaining the minimum function.

In the course of the study, the method of equivalent figurative transformations based on the laws and axioms of the algebra of logic, protocols for minimizing CNF of Boolean functions is used.

The reduction of the computational complexity of the process of minimization of the CNF of the Boolean functions by the combinatorial method according to the new established criteria has been obtained, thanks to the use of a number of features of the algorithm for finding minimal disjunctive normal forms (DNF) and CNF of logical functions, in particular

  • the use of the mathematical apparatus of transforming flowcharts with repetition allows to increase the information component of the figurative transformation with respect to the orthogonality, adjacency, uniqueness of truth table blocks;
  • equivalent figurative transformations allow with the effect to replace verbal procedures of algebraic transformations due to the greater information capacity of matrix images;
  • result of minimization is estimated on the basis of the minimal function;
  • minimal DNF or CNF of the functions are obtained regardless of the normal form of the given logical function;
  • minimization protocols for CNF of Boolean functions make up a library of protocols for the process of minimization of CNF of Boolean functions as standard procedures.

Due to the above, it is possible to optimally reduce the number of variables of a given function without losing its functionality. The effectiveness of the use of figurative transformations is demonstrated by examples of minimizing functions borrowed from other methods for the purpose of comparison.

Compared with similar known methods of minimizing Boolean functions, the proposed method allows

  • reduce the algorithmic complexity of minimizing CNF of Boolean functions;
  • increase the visibility of the minimization process of DNF or CNF of Boolean functions;
  • ensure the self-sufficiency of the combinatorial method of minimizing Boolean functions by introducing features of the minimal function and minimization on the full table of DNF and CNF.

Author Biographies

Volodymyr Riznyk, Lviv Polytechnic National University, 12, S. Bandery str., 11, Lviv, Ukraine, 79013

Doctor of Technical Sciences, Professor

Department of Control Aided Systems

Mykhailo Solomko, National University of Water and Environmental Engineering, 11, Soborna str., Rivne, Ukraine, 33028

PhD, Associate Professor

Department of Computer Engineering

References

  1. Riznyk, V., Solomko, M. (2017). Minimization of Boolean functions by combinatorial method. Technology Audit and Production Reserves, 4 (2 (36)), 49–64. doi: http://doi.org/10.15587/2312-8372.2017.108532
  2. Riznyk, V., Solomko, M. (2017). Application of super-sticking algebraic operation of variables for Boolean functions minimization by combinatorial method. Technology Audit and Production Reserves, 6 (2 (38)), 60–76. doi: http://doi.org/10.15587/2312-8372.2017.118336
  3. Riznyk, V., Solomko, M. (2018). Research of 5-bit boolean functions minimization protocols by combinatorial method. Technology Audit and Production Reserves, 4 (2 (42)), 41–52. doi: http://doi.org/10.15587/2312-8372.2018.140351
  4. Cepek, O., Kucera, P., Savicky, P. (2012). Boolean functions with a simple certificate for CNF complexity. Discrete Applied Mathematics, 160 (4-5), 365–382. doi: http://doi.org/10.1016/j.dam.2011.05.013
  5. Hemaspaandra, E., Schnoor, H. (2012). Minimization for Generalized Boolean Formulas. Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, 566–571.
  6. Boros, E., Cepek, O., Kucera, P. (2013). A decomposition method for CNF minimality proofs. Theoretical Computer Science, 510, 111–126. doi: http://doi.org/10.1016/j.tcs.2013.09.016
  7. Gursk´y, S. (2011). Minimization of Matched Formulas. WDS'11 Proceedings of Contributed Papers. Part 1, 101–105.
  8. Bernasconi, A., Ciriani, V., Luccio, F., Pagli, L. (2003). Three-level logic minimization based on function regularities. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 22 (8), 1005–1016. doi: http://doi.org/10.1109/tcad.2003.814950
  9. Nosrati, M., Karimi, R. (2011). An Algorithm for Minimizing of Boolean Functions Based on Graph DS. World Applied Programming, 1 (3), 209–214.
  10. Valli, M., Periyasamy, Dr. R., Amudhavel, J. (2017). A state of appraoches on minimization of boolean functions. Journal of Advanced Research in Dynamical and Control Systems, 12, 1322–1341. Available at: http://www.jardcs.org/abstract.php?archiveid=1323#
  11. Boyar, J., Peralta, R. (2010). A New Combinational Logic Minimization Technique with Applications to Cryptology. Lecture Notes in Computer Science. Berlin: Springer, 178–189. doi: http://doi.org/10.1007/978-3-642-13193-6_16
  12. Fiser, P., Toman, D. (2009). A Fast SOP Minimizer for Logic Funcions Described by Many Product Terms. 2009 12th Euromicro Conference on Digital System Design, Architectures, Methods and Tools. Patras. doi: http://doi.org/10.1109/dsd.2009.157
  13. Pynko, A. P. (2014). Minimal sequent calculi for monotonic chain finitely-valued logics. Bulletin of the Section of Logic, 43 (1-2), 99–112.
  14. Pyn'ko, A. P. (2017). Minimizaciya KNF chastichno-monotonnykh bulevykh funkciy. Dopovіdі Nacіonal'noi akademіi nauk Ukraini, 3, 18–21.
  15. Bulevy funkcii. Available at: http://any-book.org/download/88296.html
  16. Rytsar, B. Ye. (2015). New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification. Upravlyayushhie sistemy i mashiny, 2, 39–57. Available at: http://dspace.nbuv.gov.ua/handle/123456789/87194
  17. Rytsar, B. Ye. (2013). Minimizatsiia systemy lohichnykh funktsii metodom paralelnoho rozcheplennia koniunktermiv. Visnyk Natsionalnoho universytetu "Lvivska politekhnika". Radioelektronika ta telekomunikatsii, 766, 18–27. Available at: http://nbuv.gov.ua/UJRN/VNULPPT_2013_766_6
  18. Martyniuk, O. M. (2008). Osnovy dyskretnoi matematyky. Konspekt lektsii. Odesa: Odeskyi natsionalnyi politekhnichnyi universytet: Nauka i tekhnika, 300.

Downloads

Published

2018-05-17

How to Cite

Riznyk, V., & Solomko, M. (2018). Minimization of conjunctive normal forms of boolean functions by combinatorial method. Technology Audit and Production Reserves, 5(2(43), 42–55. https://doi.org/10.15587/2312-8372.2018.146312

Issue

Vol. 5 No. 2(43) (2018): Information and control systems

Section

Mathematical Modeling: Original Research

License

Copyright (c) 2018 Volodymyr Riznyk, Mykhailo Solomko

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.